#include<iostream>
#include<string>
#include <ctime>

using namespace std;



void InsertionSort(int arr[], int n)
{
	for (int i = 1; i < n; i++)
	{
		if (arr[i] < arr[i - 1])
		{
			int tmp = arr[i];
			int j;
			for (j = i - 1; j >= 0 && tmp < arr[j]; j--)
			{
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = tmp;
		}
	}
}


int main()
{
	//int arr[5] = { 5, 2, 8, 4, 3 };
	int arr[15] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
	//int arr[7] = { 64, 34, 25, 12, 22, 11, 90 };
	/*int arr[100] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
		11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 
		21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 
		31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 
		41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 
		51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 
		61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 
		71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 
		81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 
		91, 92, 93, 94, 95, 96, 97, 98, 99, 100 };*/


	int sz = sizeof(arr) / sizeof(arr[0]);

	for (auto e : arr)
	{
		cout << e << " ";
	}
	cout << endl;

	InsertionSort(arr, sz);

	for (auto e : arr)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}